//环形子数组的最大和
class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int sum=0;
        for(auto e:nums) sum+=e;
        int n=nums.size();
        
        vector<int>dp(n,0);
        vector<int>gp(n,0);
        dp[0]=nums[0];
        gp[0]=nums[0];
        int tmpmax=dp[0];
        int tmpmin=gp[0];
        for(int i=1;i<n;i++)
        {
            dp[i]=max(dp[i-1]+nums[i],nums[i]);
            tmpmax=dp[i]>tmpmax?dp[i]:tmpmax;
            gp[i]=min(gp[i-1]+nums[i],nums[i]);
            tmpmin=gp[i]<tmpmin?gp[i]:tmpmin;
        }
        if(sum==tmpmin) return tmpmax;//数组里全是负数 sum-tmpmin固定为0
        else if(tmpmax>(sum-tmpmin))
        return tmpmax;
        else
        return sum-tmpmin;

    }
};
//乘积为正数的最长子数组长度

class Solution {
public:
    int getMaxLen(vector<int>& nums) 
    {
        //f[i] 以i下标结尾的 乘积>0的最长子数组长度
        //g[i] 以i下标结尾的 乘积<0的最长子数组长度
        int n=nums.size();
        vector<int>f(n,0);
        vector<int>g(n,0);
        f[0]=nums[0]>0?1:0;
        g[0]=nums[0]<0?1:0;
        int res=f[0];
        for(int i=1;i<n;i++)
        {
            if(nums[i]>0)
            {
                f[i]=f[i-1]+1;
                g[i]=g[i-1]==0?0:g[i-1]+1;
                res=f[i]>res?f[i]:res;
            }
            else if(nums[i]==0)
            {
                f[i]=0;
                g[i]=0;
            }
            else
            {
                f[i]=g[i-1]==0?0:g[i-1]+1;
                g[i]=f[i-1]+1;
                res=f[i]>res?f[i]:res;
            }
        }
        return res;
    }
};